package com.zp.self.module.level_4_算法练习.算法.排序;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class IV_希尔排序_O_nXlogn__nXn {
    static int move = 0;
    @Test
    public void main() {
        int[] orderly = {3,3,4,5,6,6,9,9,12};
//        int[] arr = {5, 3, 4, 6, 3, 9, 12, 9, 6};
        int[] arr = {7, 6, 5, 4, 3, 2, 1,0};;
/*        for (int i = 0; i < 100; i++) {//打乱100次，验证排序的正确性
            猴子排序_量子级别.shuffle(arr);
            shellSort(arr);
            Assert.assertEquals(Arrays.toString(arr), Arrays.toString(orderly));
        }*/
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
    题目：希尔排序：时间：O(n^(1.3—2)) 、空间：O(1)、顺序不稳定

    分析：1.也是一种插入排序。简单的插入排序可能存在的问题：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
            为了改进，提出了希尔排序算法。
          2.希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
            随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
          3.希尔排序的基本步骤：
                    在此选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。
                    希尔排序的增量序列的选择与证明是个数学难题，选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，
                    但其实这个增量序列不是最优的。此处做示例使用希尔增量。

     **/
    //希尔排序
    public int[] shellSort(int[] arr) {
        // 间隔为inc增量间隔为len/2 ,分成了arr.length / 2 组，每一组都是插入排序
        for (int inc = arr.length/2; inc >0; inc=inc/2) {
            // 每一趟采用插入排序 等价于上面的插入排序
            for (int j = inc; j< arr.length; j++) {
                //第一组：0、inc、2inc、3inc ....为一组 第一个数已经排好了，所以从inc开始。第二组：j++;
                //所以：每次进入循环都是当前组插入一个元素，j++轮到下一组插入元素
                //cur：当前值    proIndex:指向前一个 即已排序末端
                int cur = arr[j] ,proIndex=j-inc;
                while (proIndex>-1 && arr[proIndex]>cur){   //--这里对比插入排序：只需要与前面一个值比较，交换
                    arr[proIndex+inc] = arr[proIndex];
                    proIndex-=inc;
                    move++;
                }
                arr[proIndex+inc] = cur;
            }
        }
        System.out.println("移动次数："+move);
        return arr;
    }
}
